class Solution(object):
    def calculate(self, s):
        """
        :type s: str
        :rtype: int
        """
        # s to mid
        opDict = {'-':1, '+':1, '*':3, '/':3, '(':10, ')':10}
        mid = []
        acc = ''
        for c in s:
            if c in opDict:
                if len(acc)!=0:
                    mid.append(int(acc))
                    acc=''
                mid.append(c)
            elif c==' ':
                continue
            else:
                acc+=c
        if len(acc)!=0:
            mid.append(int(acc))
            acc=''

        # mid to back
        op = []
        back = []
        for e in mid:
            if isinstance(e, int):
                back.append(e)
            elif e==')':
                while op[-1]!='(':
                    back.append(op[-1])
                    op.pop()
                op.pop()
            else:
                while len(op)!=0 and op[-1]!='(' and opDict[op[-1]]>=opDict[e]:
                    back.append(op[-1])
                    op.pop()
                op.append(e)
        while len(op)!=0:
            back.append(op[-1])
            op.pop()
        
        # clac back
        factor = []
        for e in back:
            if isinstance(e, int):
                factor.append(e)
            else:
                f1 = factor[-1]
                factor.pop()
                f0 = factor[-1]
                factor.pop()
                if e=='+':
                    factor.append(f0+f1)
                elif e=='-':
                    factor.append(f0-f1)
                elif e=='*':
                    factor.append(f0*f1)
                elif e=='/':
                    factor.append(f0//f1)
        return factor[0]

print(Solution().calculate(" 2-1 + 2 "))